function Quick1(arr) {
	if (arr.length < 2) return arr

	// 取基准点
	const midIndex = Math.floor(arr.length / 2)
	const mid = arr.splice(midIndex, 1)[0]
	const left = []
	const right = []
	for(let i = 0; i < arr.length; i++) {
		const cur = arr[i]
		if (cur < mid) {
			left.push(cur)
		} else {
			right.push(cur)
		}
	}

	return Quick1(left).concat(mid, Quick1(right))
}

function quickSort(arr, left, right) {
	let len = arr.length,
		partitionIndex

	left = typeof left !== 'number' ? 0 : left
	right = typeof right !== 'number' ? len - 1 : right

	if (left < right) {
		partitionIndex = partition(arr, left, right)
		quickSort(arr, left, partitionIndex - 1)
		quickSort(arr, partitionIndex + 1, right)
	}

	return arr
}

const partition = (arr, left, right) => {
	// 分区操作
	let pivot = left,
		index = pivot + 1

	for (let i = index; i <= right; i++) {
		if (arr[i] < arr[pivot]) {
			swap(arr, i, index)
			index++
		}
	}
	swap(arr, pivot, index - 1)
	return index - 1
}

const swap = (arr, i, j) => {
	let temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp
}

module.exports = { Quick1, quickSort }